package graph2.weight.dijkstra;

import graph.weight.prim2.IndexMinHeap;
import graph2.weight.Edge;
import graph2.weight.WeightedGraph;

import java.util.LinkedList;

/**
 * 有权图的最短路径
 */
public class DijkstraReview<Weight extends Number & Comparable> {

    /**
     * 指向顶点的权重最小的边
     */
    private Edge<Weight>[] from;

    /**
     * 最短路径的原点
     */
    private int src;

    /**
     * 已经得到最短路径
     */
    private boolean[] marked;

    /**
     * 索引是节点 值是指向此索引的最短边
     */
    private IndexMinHeap<Double> indexMinHeap;

    /**
     * 图的引用
     */
    private WeightedGraph graph;

    /**
     * 到某个节点的权重
     */
    private double[] disTo;


    public DijkstraReview(WeightedGraph graph, int src) {
        this.graph = graph;
        this.src = src;
        from = (Edge<Weight>[]) new Edge[graph.V()];
        marked = new boolean[graph.V()];
        indexMinHeap = new IndexMinHeap<>(graph.V());
        disTo = new double[graph.V()];

        visit(src);
        while (!indexMinHeap.isEmpty()) {
            int index = indexMinHeap.extractMinIndex();
            visit(index);
        }
    }

    private void visit(int i) {
        marked[i] = true;
        Iterable<Edge<Weight>> adj = graph.adj(i);
        for (Edge<Weight> edge : adj) {
            int other = edge.other(i);
            if (!marked[i]) {
                if (from[other] == null || disTo[other] > disTo[i] + edge.weight().doubleValue()) {
                    disTo[other] = disTo[i] + edge.weight().doubleValue();
                    from[other] = edge;
                    if (indexMinHeap.contain(other)) {
                        indexMinHeap.insert(other, disTo[other]);
                    } else {
                        indexMinHeap.change(other, disTo[other]);
                    }

                }
            }

        }
    }


    /**
     * 是否有路
     *
     * @return
     */
    public boolean hasPath(int v) {
        return marked[v];
    }

    /**
     * 返回一个点的所有路径
     *
     * @param v
     * @return
     */
    public LinkedList path(int v) {
        LinkedList<Edge> edges = new LinkedList<>();
        while (from[v] != null) {
            edges.add(from[v]);
            v = from[v].other(v);
        }
        return edges;
    }

    /**
     * 打印一个路径
     *
     * @param v
     * @return
     */
    public void showPath(int v) {
        LinkedList path = path(v);
        System.out.println(path + "->" + v);
    }

}
